#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
const int N = 1010;
int l[N][N], r[N][N], a[N];
int t, n;
int main()
{
    cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 0; i < n; i++) cin >> a[i];
        for (int len = 1; len <= n; len++)
        {
            for (int i = 0; i + len - 1 < n; i++)
            {
                int j = i + len - 1;
                if (len == 1) l[i][j] = r[i][j] = a[i];
                else
                {
                    int L = l[i][j - 1], R = r[i][j - 1], x = a[j];
                    if (R == x) l[i][j] = 0;
                    else if ((x < L && x < R) || (x > L && x > R)) l[i][j] = x;
                    else if (L > R) l[i][j] = x - 1;
                    else l[i][j] = x + 1;

                    L = l[i + 1][j], R = r[i + 1][j], x = a[i];
                    if (L == x) r[i][j] = 0;
                    else if ((x < L && x < R) || (x > L && x > R)) r[i][j] = x;
                    else if (R > L) r[i][j] = x - 1;
                    else r[i][j] = x + 1;
                }
            }
        }
        if (n == 1) cout << "1" << endl;
        else cout << (l[1][n - 1] != a[0]) << endl;
    }
    return 0;
}